import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 47. 全排列 II
 * <a href="https://leetcode.cn/problems/permutations-ii/">...</a>
 * User: DELL
 * Date: 2023-07-16
 * Time: 23:31
 */
public class Solution {
    /**
     * 解题思路: (dfs+回溯)
     * 本题主要的问题就是如何去除重复的结果集,其实重复的结果集产生的原因就是
     * 在 dfs 的同一层中,重复添加了重复的数字,我们需要做的就是在 dfs 的每
     * 一层中,重复的可添加的数字只添加一次即可,因此在 dfs 中添加数字的时候,
     * 可以只添加重复数字的第一个未添加的数字
     * 即  !(i > 0 && nums[i] == nums[i-1] && !flags[i-1])
     * 这样子处理的本质是确定了重复数字的顺序,即假设有重复数字 3 3 3,
     * 这样子处理以后,想要添加 3,就必须按顺序添加,即第一个,添加了第一个
     * 后,后续才能添加第二个.....,其实就是给这三个重复的 3 固定了顺序,
     * 因此就不会出现重复的结果集了
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        // 题目保证输入合法,因此不需要要进行合法性检验
        boolean[] flags = new boolean[nums.length];
        Deque<Integer> stack = new LinkedList<>();
        // 排序后,方便后续dfs去重
        Arrays.sort(nums);
        dfs(res,nums,flags,stack);
        return res;
    }

    /**
     * dfs 遍历所有不同的结果集
     * @param res
     * @param nums
     * @param flags
     * @param stack
     */
    private void dfs(List<List<Integer>> res, int[] nums, boolean[] flags, Deque<Integer> stack) {
        // 递归结束条件
        if (stack.size() == nums.length) {
            res.add(new ArrayList<>(stack));
        }
        // 递归添加每一个不重复项
        for (int i = 0; i < nums.length; i++) {
            // 每一次只添加第一个的 未添加的连续数字
            if (flags[i] || (i > 0 && nums[i] == nums[i-1] && !flags[i-1])) {
                continue;
            }
            flags[i] = true;
            stack.push(nums[i]);
            dfs(res,nums,flags,stack);
            stack.pop();
            flags[i] = false;
        }
    }
}